package com.chj.jz.dp.class03;

public class Code04_HouseRobberII {
	/**
	 * @param A:
	 *            An array of non-negative integers
	 * @return: The maximum amount of money you can rob tonight
	 */
	public static long houseRobberII(int[] A) {
		// write your code here

		int n = A.length;
		if (n == 0) {
			return 0;
		}

		if (n == 1) {
			return A[0];
		}

		int[] nums = new int[n - 1];
		int res = Integer.MIN_VALUE;
		int i;
		
		for (i = 0; i < n - 1; i++) {
			nums[i] = A[i];
		}
		res = Math.max(res, calc(nums));

		for (i = 0; i < n - 1; i++) {
			nums[i] = A[i + 1];
		}
		res = Math.max(res, calc(nums));

		
		return res;
	}

	public static int calc(int[] A) {
		// write your code here

		int n = A.length;
		if (n == 0) {
			return 0;
		}

		if (n == 1) {
			return A[0];
		}

		int old = 0;
		int now = A[0];
		for (int i = 2; i <= n; i++) {
			int t = Math.max(now, old + A[i - 1]);
			old = now;
			now = t;
		}

		return now;
	}


	
	public static void main(String[] args) {
		{
			int[] arr = new int[] { 3, 6, 4 };
			System.out.println(houseRobberII(arr));
		}
		{
			int[] arr = new int[] { 2, 3, 2, 3 };
			System.out.println(houseRobberII(arr));
		}
	}
}
